﻿// 203. 同余方程.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*

https://www.acwing.com/problem/content/205/

求关于 x 的同余方程 ax≡1(modb) 的最小正整数解。

输入格式
输入只有一行，包含两个正整数 a,b，用一个空格隔开。

输出格式
输出只有一行，包含一个正整数 x，表示最小正整数解。

输入数据保证一定有解。

数据范围
2≤a,b≤2×109
输入样例：
3 10
输出样例：
7
*/

#include <iostream>

using namespace std;


// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int& x, int& y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}


int main()
{
    int a, b; cin >> a >> b;
    int x, y;
    exgcd(a, b, x, y);

    cout << (x % b + b) % b << endl;

    return 0;
}

 